﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Liquid.Collections {
	/// <summary>
	/// An implementation of the standard Gap Buffer data structure.
	/// Manages an array that may have a gap in it,
	/// into which items can be inserted.
	/// </summary>
	/// <typeparam name="T">The type of items in the buffer</typeparam>
	public sealed class GapBuffer<T> : BufferBase<T> {
		const bool _needClear = true; // TODO: Make GapBuffer<T>._needClear dynamic based on whether T contains garbage-collectible references

		/// <summary>
		/// Creates a <see cref="GapBuffer&lt;T&gt;"/> using the specified array as a buffer.
		/// </summary>
		/// <param name="array">The array.</param>
		/// <returns>The created <see cref="GapBuffer&lt;T&gt;"/></returns>
		public static GapBuffer<T> FromArray(T[] array) {
			return new GapBuffer<T>(array, 0, 0, EqualityComparer<T>.Default);
		}
		/// <summary>
		/// Creates a <see cref="GapBuffer&lt;T&gt;"/> using the specified array as a buffer.
		/// </summary>
		/// <param name="array">The array.</param>
		/// <param name="comparer">The comparer.</param>
		/// <returns>
		/// The created <see cref="GapBuffer&lt;T&gt;"/>
		/// </returns>
		public static GapBuffer<T> FromArray(T[] array, IEqualityComparer<T> comparer) {
			return new GapBuffer<T>(array, 0, 0, comparer);
		}
		/// <summary>
		/// Creates a <see cref="GapBuffer&lt;T&gt;"/> using the specified array as a buffer.
		/// </summary>
		/// <param name="array">The array.</param>
		/// <param name="gapStart">The index in the array where the gap starts.</param>
		/// <param name="gapLength">Length of the gap.</param>
		/// <returns>
		/// The created <see cref="GapBuffer&lt;T&gt;"/>
		/// </returns>
		public static GapBuffer<T> FromArray(T[] array, int gapStart, int gapLength) {
			return new GapBuffer<T>(array, gapStart, gapLength, EqualityComparer<T>.Default);
		}
		/// <summary>
		/// Creates a <see cref="GapBuffer&lt;T&gt;"/> using the specified array as a buffer.
		/// </summary>
		/// <param name="array">The array.</param>
		/// <param name="gapStart">The index in the array where the gap starts.</param>
		/// <param name="gapLength">Length of the gap.</param>
		/// <param name="comparer">The comparer.</param>
		/// <returns>
		/// The created <see cref="GapBuffer&lt;T&gt;"/>
		/// </returns>
		public static GapBuffer<T> FromArray(T[] array, int gapStart, int gapLength, IEqualityComparer<T> comparer) {
			return new GapBuffer<T>(array, gapStart, gapLength, comparer);
		}

		private GapBuffer(T[] array, int gapStart, int gapLength, IEqualityComparer<T> comparer)
			: base(comparer) {
			this.buffer = array;
			this.preIndex = gapStart;
			this.postIndex = gapStart + gapLength;
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="GapBuffer&lt;T&gt;"/> class.
		/// </summary>
		public GapBuffer() : this(1) { }
		/// <summary>
		/// Initializes a new instance of the <see cref="GapBuffer&lt;T&gt;"/> class, with the specified initial capacity.
		/// </summary>
		/// <param name="capacity">The initial capacity of the buffer.</param>
		public GapBuffer(int capacity)
			: this(capacity, EqualityComparer<T>.Default) { }

		/// <summary>
		/// Initializes a new instance of the <see cref="GapBuffer&lt;T&gt;"/> class, with the specified comparer.
		/// </summary>
		/// <param name="comparer">The comparer.</param>
		public GapBuffer(IEqualityComparer<T> comparer) : this(1, comparer) { }
		/// <summary>
		/// Initializes a new instance of the <see cref="GapBuffer&lt;T&gt;"/> class, with the specified initial capacity and comparer.
		/// </summary>
		/// <param name="capacity">The initial capacity of the buffer.</param>
		/// <param name="comparer">The comparer.</param>
		public GapBuffer(int capacity, IEqualityComparer<T> comparer)
			: base(comparer) {
			buffer = new T[capacity];
			preIndex = 0;
			postIndex = capacity;
		}

		T[] buffer;
		int preIndex, postIndex;
		int generation;

		private void Resize(int desiredLength) {
			T[] newBuffer = new T[desiredLength];
			Array.Copy(
				buffer,
				0,
				newBuffer,
				0,
				preIndex
			);
			int postLength = buffer.Length - postIndex;
			int newPostIndex = desiredLength - postLength;
			Array.Copy(
				buffer,
				postIndex,
				newBuffer,
				newPostIndex,
				postLength
			);
			postIndex = newPostIndex;
			buffer = newBuffer;
			generation++;
		}
		private void MoveCursor(int index) {
			if (index == preIndex) {
				return; // Cursor already in that position
			} else if (index < preIndex) {
				int moveLength = preIndex - index;
				Array.Copy(
					buffer,
					index,
					buffer,
					postIndex - moveLength,
					moveLength
				);
				preIndex -= moveLength;
				postIndex -= moveLength;
				ClearGap();
				generation++;
			} else {
				int moveLength = index - preIndex;
				Array.Copy(
					buffer,
					postIndex,
					buffer,
					preIndex,
					moveLength
				);
				preIndex += moveLength;
				postIndex += moveLength;
				ClearGap();
				generation++;
			}
		}
		private void ClearGap() {
			if (_needClear)
				Array.Clear(
					buffer,
					preIndex,
					postIndex - preIndex
				);
		}
		private int ResizePolicy(int minimumLength) {
			// TODO: Is GapBuffer<T>.ResizePolicy() correct?
			return Math.Max(
				minimumLength,
				buffer.Length * 2
			);
		}

		/// <summary>
		/// Gets or sets the current position.
		/// </summary>
		/// <value>The position.</value>
		public override int Position {
			get { return preIndex; }
			set { MoveCursor(value); }
		}
		/// <summary>
		/// Gets or sets the capacity of the buffer.
		/// </summary>
		/// <value>The capacity.</value>
		public override int Capacity {
			get { return buffer.Length; }
			set {
				if (value < Count)
					throw new ArgumentOutOfRangeException("value", "Can not set capacity to a value smaller than the number of current items");
				Resize(value);
			}
		}

		/// <summary>
		/// Inserts an item into the buffer at the current position.
		/// </summary>
		/// <param name="item">The item to insert.</param>
		public override void Insert(T item) {
			if (preIndex >= postIndex) {
				Resize(ResizePolicy(Count + 1));
			}
			buffer[preIndex++] = item;
			generation++;
		}
		/// <summary>
		/// Inserts the range.
		/// </summary>
		/// <param name="range">The range.</param>
		public override void InsertRange(IEnumerable<T> range) {
			if (range is IList<T>) {
				InsertRange((IList<T>)range);
			} else {
				InsertRange(range.ToList());
			}
			generation++;
		}
		/// <summary>
		/// Inserts a range of items into the buffer at the current position.
		/// </summary>
		/// <param name="list">The items to insert.</param>
		public override void InsertRange(IList<T> list) {
			if (list is T[]) {
				InsertRange((T[])list);
			} else {
				int length = list.Count;
				if (preIndex + list.Count > postIndex) {
					Resize(ResizePolicy(Count + length));
				}
				for (int i = 0; i < list.Count; i++) {
					buffer[preIndex + i] = list[i];
				}
				preIndex += length;
				generation++;
			}
		}
		/// <summary>
		/// Inserts a range of items into the buffer at the current position.
		/// </summary>
		/// <param name="array">The items to insert.</param>
		public override void InsertRange(T[] array) {
			int length = array.Length;
			if (preIndex + length > postIndex) {
				Resize(ResizePolicy(Count + length));
			}
			Array.Copy(
				array, 0,
				buffer, preIndex,
				length
			);
			preIndex += length;
			generation++;
		}

		/// <summary>
		/// Deletes the item after the current position from the buffer.
		/// </summary>
		public override void DeleteNext() {
			if (postIndex >= buffer.Length)
				throw new ArgumentOutOfRangeException("Cursor", "Can not delete an item after the end of the buffer");
			if (_needClear)
				buffer[postIndex] = default(T);
			postIndex++;
			generation++;
		}
		/// <summary>
		/// Deletes the item before the current position from the buffer.
		/// </summary>
		public override void DeletePrevious() {
			if (preIndex == 0)
				throw new ArgumentOutOfRangeException("Cursor", "Can not delete an item before the start of the buffer");
			preIndex--;
			if (_needClear)
				buffer[preIndex] = default(T);
			generation++;
		}

		/// <summary>
		/// Deletes a number of items from the buffer, after the current position.
		/// </summary>
		/// <param name="count">The number of items to delete.</param>
		public override void DeleteNext(int count) {
			if (count < 0)
				throw new ArgumentOutOfRangeException("count");
			if (count > 0) {
				if (postIndex + count >= buffer.Length)
					throw new ArgumentOutOfRangeException("Cursor", "Can not delete an item after the end of the buffer");
				if (_needClear)
					Array.Clear(buffer, postIndex, count);
				postIndex += count;
				generation++;
			}
		}
		/// <summary>
		/// Deletes a number of items from the buffer, before the current position.
		/// </summary>
		/// <param name="count">The number of items to delete.</param>
		public override void DeletePrevious(int count) {
			if (count < 0)
				throw new ArgumentOutOfRangeException("count");
			if (count > 0) {
				if (preIndex < count)
					throw new ArgumentOutOfRangeException("Cursor", "Can not delete an item before the start of the buffer");
				preIndex -= count;
				if (_needClear)
					Array.Clear(buffer, preIndex, count);
				generation++;
			}
		}

		/// <summary>
		/// Implements the actual copying of items from the buffer into an array.
		/// </summary>
		/// <param name="startIndex">The index in the buffer to start copying from.</param>
		/// <param name="array">The array to copy into.</param>
		/// <param name="arrayIndex">Index in the array to copy to.</param>
		/// <param name="count">The number of items to copy.</param>
		protected override void CopyBufferCore(int startIndex, T[] array, int arrayIndex, int count) {
			if (startIndex < preIndex) {
				int fromPre = preIndex - startIndex;
				Array.Copy(
					buffer,
					startIndex,
					array,
					arrayIndex,
					Math.Min(fromPre, count)
				);
				if (startIndex + count > preIndex)
					Array.Copy(
						buffer,
						postIndex,
						array,
						arrayIndex + fromPre,
						count - fromPre
					);
			} else {
				int index = startIndex + postIndex;
				Array.Copy(
					buffer,
					startIndex,
					array,
					arrayIndex,
					count
				);
			}
		}

		#region IList<T> Members

		/// <summary>
		/// Determines the index of a specific item in the <see cref="T:Liquid.Collections.BufferBase`1"/>.
		/// </summary>
		/// <param name="item">The object to locate in the <see cref="T:Liquid.Collections.BufferBase`1"/>.</param>
		/// <returns>
		/// The index of <paramref name="item"/> if found in the list; otherwise, -1.
		/// </returns>
		public override int IndexOf(T item) {
			for (int i = 0; i < preIndex; i++) {
				if (Comparer.Equals(buffer[i], item))
					return i;
			}
			int length = buffer.Length;
			for (int i = postIndex; i < length; i++) {
				if (Comparer.Equals(buffer[i], item))
					return i - postIndex;
			}
			return -1;
		}

		/// <summary>
		/// Gets or sets the item at the specified index.
		/// </summary>
		/// <value></value>
		public override T this[int index] {
			get {
				int length = Count;
				if (index < 0)
					throw new ArgumentOutOfRangeException("index");
				else if (index >= length - postIndex)
					throw new ArgumentOutOfRangeException("index");
				else if (index < preIndex)
					return buffer[index];
				else
					return buffer[index + postIndex];
			}
			set {
				int length = Count;
				if (index < 0)
					throw new ArgumentOutOfRangeException("index");
				else if (index >= length - postIndex)
					throw new ArgumentOutOfRangeException("index");
				else if (index < preIndex)
					buffer[index] = value;
				else
					buffer[index + postIndex] = value;
			}
		}

		#endregion

		#region ICollection<T> Members

		/// <summary>
		/// Removes all items from the <see cref="T:Liquid.Collections.BufferBase`1"/>.
		/// </summary>
		/// <exception cref="T:System.NotSupportedException">The <see cref="T:Liquid.Collections.BufferBase`1"/> is read-only. </exception>
		public override void Clear() {
			preIndex = 0; postIndex = 0;
			ClearGap();
			generation++;
		}

		/// <summary>
		/// Determines whether the <see cref="T:Liquid.Collections.BufferBase`1"/> contains a specific value.
		/// </summary>
		/// <param name="item">The object to locate in the <see cref="T:Liquid.Collections.BufferBase`1"/>.</param>
		/// <returns>
		/// true if <paramref name="item"/> is found in the <see cref="T:Liquid.Collections.BufferBase`1"/>; otherwise, false.
		/// </returns>
		public override bool Contains(T item) {
			return IndexOf(item) >= 0;
		}

		/// <summary>
		/// Copies the elements of the <see cref="T:Liquid.Collections.BufferBase`1"/> to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index.
		/// </summary>
		/// <param name="array">The one-dimensional <see cref="T:System.Array"/> that is the destination of the elements copied from <see cref="T:Liquid.Collections.BufferBase`1"/>. The <see cref="T:System.Array"/> must have zero-based indexing.</param>
		/// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param>
		/// <exception cref="T:System.ArgumentNullException">
		/// 	<paramref name="array"/> is null.</exception>
		/// <exception cref="T:System.ArgumentOutOfRangeException">
		/// 	<paramref name="arrayIndex"/> is less than 0.</exception>
		/// <exception cref="T:System.ArgumentException">
		/// 	<paramref name="array"/> is multidimensional.-or-<paramref name="arrayIndex"/> is equal to or greater than the length of <paramref name="array"/>.-or-The number of elements in the source <see cref="T:Liquid.Collections.BufferBase`1"/> is greater than the available space from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.-or-Type <paramref name="T"/> cannot be cast automatically to the type of the destination <paramref name="array"/>.</exception>
		public override void CopyTo(T[] array, int arrayIndex) {
			if (array.Length < arrayIndex + Count)
				throw new ArgumentException("arrayIndex", "Array is not large enough to copy to the specified index");
			Array.Copy(
				buffer,
				0,
				array,
				arrayIndex,
				preIndex
			);
			Array.Copy(
				buffer,
				postIndex,
				array,
				arrayIndex + preIndex,
				buffer.Length - postIndex
			);
		}

		/// <summary>
		/// Gets the number of elements contained in the <see cref="T:Liquid.Collections.BufferBase`1"/>.
		/// </summary>
		/// <value></value>
		/// <returns>The number of elements contained in the <see cref="T:Liquid.Collections.BufferBase`1"/>.</returns>
		public override int Count {
			get { return buffer.Length - (postIndex - preIndex); }
		}

		#endregion

		class GapBufferEnumerator : IEnumerator<T> {
			GapBuffer<T> gapBuffer;
			int generation;
			T[] buffer;
			int length;
			int preIndex, postIndex;
			int index;

			public GapBufferEnumerator(GapBuffer<T> gapBuffer) {
				this.gapBuffer = gapBuffer;
				this.generation = gapBuffer.generation;
				this.buffer = gapBuffer.buffer;
				this.length = gapBuffer.buffer.Length;
				this.preIndex = gapBuffer.preIndex;
				this.postIndex = gapBuffer.postIndex;
				this.index = -1;
			}

			#region IEnumerator<T> Members

			public T Current {
				get { return buffer[index]; }
			}

			#endregion

			#region IDisposable Members

			public void Dispose() { }

			#endregion

			#region IEnumerator Members

			object IEnumerator.Current {
				get { return buffer[index]; }
			}

			public bool MoveNext() {
				if (generation != gapBuffer.generation)
					throw new InvalidOperationException("The GapBuffer was modified");
				index++;
				if (index > preIndex && index < postIndex)
					index = postIndex;
				if (index >= buffer.Length)
					return false;
				return true;
			}

			public void Reset() {
				index = -1;
			}

			#endregion
		}

		#region IEnumerable<T> Members

		/// <summary>
		/// Returns an enumerator that iterates through the collection.
		/// </summary>
		/// <returns>
		/// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
		/// </returns>
		public override IEnumerator<T> GetEnumerator() {
			return new GapBufferEnumerator(this);
		}

		#endregion
	}
}
